package top.minuy.structure.graph.matching;

import top.minuy.structure.graph.bipartition.dfs.BipartitionDetection;
import top.minuy.structure.graph.representations.table.Graph;


/**
 * 匈牙利最大匹配算法，深度优先遍历
 * O(V*E)
 *
 * @author Minuy
 * @time 8:50
 * @date 2021/11/30
 */
public class HungarianDFS {

    private Graph g; // 图
    private int[] matching; // 匹配数组
    private int maxMatching; // 最大匹配值
    private boolean[] isVisited;

    public HungarianDFS(Graph g) {
        this.g = g;

        if (g.isDirected()) {
            throw new IllegalArgumentException("BipartiteMatching only works in undirected graph.");
        }

        BipartitionDetection bd = new BipartitionDetection(g);
        if (!bd.isBipartition()) {
            throw new IllegalArgumentException("BipartiteMatching only works for bipartite graph.");
        }

        maxMatching = 0;
        matching = new int[g.V()];
        for (int i = 0; i < g.V(); i++) {
            matching[i] = -1;
        }

        isVisited = new boolean[g.V()];

        for (int v = 0; v < g.V(); v++) {
            // 没有匹配，并且是这边的
            if (matching[v] == -1 && bd.isBlue(v)) {
                for (int i = 0; i < g.V(); i++) {
                    isVisited[i] = false;
                }
                // Arrays.fill(isVisited, false);
                if (dfs(v)) {
                    maxMatching++;
                }
            }
        }
    }

    /**
     * 深度优先遍历匹配算法
     *
     * @param v         要检测的点
     * @return boolean 是否匹配成功
     * @author Minuy
     * @date 2021/11/30 8:23
     */
    private boolean dfs(int v) {
        isVisited[v] = true;

        for (int w : g.adj(v)) {
            if (!isVisited[w]) {
                // 因为我们跳过了w，所以w也算访问了
                isVisited[w] = true;
                /* if (matching[w] == -1) {
                    matching[w] = v;
                    matching[v] = w;
                    return true;
                } else {
                    if (dfs(matching[w], isVisited)) {
                        matching[w] = v;
                        matching[v] = w;
                        return true;
                    }
                }*/

                // 上面的逻辑可以压缩成这样
                if (matching[w] == -1 || dfs(matching[w])) {
                    matching[w] = v;
                    matching[v] = w;
                    return true;
                }
            }
        }

        return false;
    }

    /**
     * 获取最大匹配
     *
     * @return int 最大匹配
     * @author Minuy
     * @date 2021/11/29 21:37
     */
    public int maxMatching() {
        return maxMatching;
    }

    /**
     * 查看是否是完全匹配
     *
     * @return boolean 是否是完全匹配
     * @author Minuy
     * @date 2021/11/29 21:38
     */
    public boolean isPerfectMatching() {
        return maxMatching * 2 == g.V();
    }

    /**
     * 获取对应的匹配点
     *
     * @param v 顶点v
     * @return int 对应的顶点v的匹配点
     * @author Minuy
     * @date 2021/11/30 8:26
     */
    public int matching(int v) {
        g.validateVertex(v);
        return matching[v];
    }

}
